package com.my.code.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 桶排序<br/>
 * 桶排序是计数排序的升级版，它利用函数的映射关系，高效与否的关键就在于这个映射函数的确定。<p>
 * 划分多个范围相同的区间，每个子区间自排序，最后合并。<p>
 * 桶排序的关键在于待排序数组的值分布区间均匀。如果都落到一个桶中，则没有意义。
 *
 * @author zzl
 * @date 2020/10/16
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {//从1开始
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        int bucketNum = 4;//桶的数量是关键
        List<List<Integer>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new ArrayList<>());
        }
        int base = (max - min + 1) / bucketNum;//一个基数用于划分桶内的范围
        for (int val : arr) {
            int num = (val - min) / base;
            bucketList.get(num).add(val);
        }

        for (List<Integer> range : bucketList) {
            Collections.sort(range);
        }

        int index = 0;
        for (List<Integer> range : bucketList) {
            for (Integer val : range) {
                arr[index++] = val;
            }
        }

    }

}
